
#include "convex.h"





void ConvexMeshBuilder::operator()(uint32_t numPlanes, float scale) {

	if (numPlanes < 4)
		return; // todo: handle degenerate cases

	HalfedgeMesh mesh;

	// gather points (planes, that is)
	mesh.mPoints.reserve(numPlanes);
	for (uint32_t i = 0; i < numPlanes; ++i)
		mesh.mPoints.push_back(Vec4(mPlanes[i].x, mPlanes[i].y, mPlanes[i].z, mPlanes[i].w));

	// initialize to tetrahedron
	mesh.addTriangle(0, 1, 2);
	mesh.addTriangle(0, 3, 1);
	mesh.addTriangle(1, 3, 2);
	mesh.addTriangle(2, 3, 0);

	// flip if inside-out
	if (mesh.visible(3, 0))
		std::swap(mesh.mPoints[0], mesh.mPoints[1]);

	// iterate through remaining points
	for (uint16_t i = 4; i < mesh.mPoints.size(); ++i)
	{
		// remove any visible triangle
		uint16_t v0 = sInvalid;
		for (uint16_t j = 0; j < mesh.mFaces.size(); ++j)
		{
			if (mesh.visible(i, j))
				v0 = Min(v0, mesh.removeTriangle(j));
		}

		if (v0 == sInvalid)
			continue; // no triangle removed

		if (!mesh.mNumTriangles)
			return; // empty mesh

		// find non-deleted boundary vertex
		for (uint16_t h = 0; mesh.mVertices[v0] == sInvalid; h += 2)
		{
			if ((mesh.mHalfedges[h].mFace == sInvalid) ^
				(mesh.mHalfedges[h + 1].mFace == sInvalid))
			{
				v0 = mesh.mHalfedges[h].mVertex;
			}
		}

		// tesselate hole
		uint16_t start = v0;
		do {
			uint16_t h = mesh.mVertices[v0];
			uint16_t v1 = mesh.mHalfedges[h].mVertex;
			mesh.addTriangle(v0, v1, i);
			v0 = v1;
		} while (v0 != start && mesh.mNumTriangles < 200);

		if (mesh.mNumTriangles == 200)
		{
			return;
		}
	}

	// convert triangles to vertices (intersection of 3 planes)
	std::vector<uint32_t> face2Vertex(mesh.mFaces.size());
	for (uint32_t i = 0; i < mesh.mFaces.size(); ++i)
	{
		face2Vertex[i] = uint32_t(mVertices.size());

		uint16_t h = mesh.mFaces[i];
		if (h == sInvalid)
			continue;

		uint16_t v0 = mesh.mHalfedges[h].mVertex;
		h = mesh.mHalfedges[h].mNext;
		uint16_t v1 = mesh.mHalfedges[h].mVertex;
		h = mesh.mHalfedges[h].mNext;
		uint16_t v2 = mesh.mHalfedges[h].mVertex;

		mVertices.push_back(intersect(mesh.mPoints[v0], mesh.mPoints[v1], mesh.mPoints[v2]));
	}

	// convert vertices to polygons (face one-ring)
	for (uint32_t i = 0; i < mesh.mVertices.size(); ++i)
	{
		uint16_t h = mesh.mVertices[i];
		if (h == sInvalid || mesh.mHalfedges[h].mFace == sInvalid)
			continue;

		uint16_t v0 = face2Vertex[mesh.mHalfedges[h].mFace];
		h = mesh.mHalfedges[h].mPrev ^ 1;
		if (h == sInvalid || mesh.mHalfedges[h].mFace == sInvalid)
			continue;

		uint16_t v1 = face2Vertex[mesh.mHalfedges[h].mFace];

		while (mIndices.size() < 1000)
		{
			h = mesh.mHalfedges[h].mPrev ^ 1;
			if (h == sInvalid || mesh.mHalfedges[h].mFace == sInvalid)
				continue;

			uint16_t v2 = face2Vertex[mesh.mHalfedges[h].mFace];

			if (v0 == v2)
				break;

			mIndices.push_back(v0);
			mIndices.push_back(v2);
			mIndices.push_back(v1);

			v1 = v2;
		}

	}
}













